/**
* @description: 879. 盈利计划
* @author hewei
* @date 2022/10/8 14:19
* @version 1.0
*/

public class ProfitableSchemes {

    public static void main(String[] args) {
        int[] group = {18,58,88,52,54,13,50,66,83,61,100,54,60,80,1,19,78,54,67,20,57,46,12,6,14,43,64,81,30,60,48,53,86,71,51,23,71,87,95,69,11,12,41,36,69,89,91,10,98,31,67,85,16,83,83,14,14,71,33,5,40,61,22,19,34,70,50,21,91,77,4,36,16,38,56,23,68,51,71,38,63,52,14,47,25,57,95,35,58,32,1,39,48,33,89,9,1,95,90,78};
        int[] profit = {96,77,37,98,66,44,18,37,47,9,38,82,74,12,71,31,80,64,15,45,85,52,70,53,94,90,90,14,98,22,33,39,18,22,10,46,6,19,25,50,33,15,63,93,35,0,76,44,37,68,35,80,70,66,4,88,66,93,49,19,25,90,21,59,17,40,46,79,5,41,2,37,27,92,0,53,57,91,75,0,42,100,16,97,83,75,57,61,73,21,63,97,75,95,84,14,98,47,0,13};
        System.out.println(new ProfitableSchemes().profitableSchemes(100,100,group,profit));
    }

    public int profitableSchemes1(int n, int minProfit, int[] group, int[] profit) {
        int sum = 0;
        for (int i : profit) {
            sum += i;
        }
        int mod = (int) (1e9 + 7);
        int[][] dp = new int[sum + 1][n + 1];
        dp[0][0] = 1;
        for (int i = 0; i < profit.length; i++) {
            for (int j = sum; j >= profit[i]; j--) {
                for (int k = n; k >= group[i]; k--) {
                    dp[j][k] = (dp[j][k] + dp[j - profit[i]][k - group[i]]) % mod;
                }
            }
        }
        int ans = 0;
        for (int i = minProfit; i < sum + 1; i++) {
            for (int j = 0; j < n + 1; j++) {
                ans = (ans + dp[i][j]) % mod;
            }
        }
        return ans;
    }

    public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) {
        int mod = (int) (1e9 + 7);
        int[][] dp = new int[n + 1][minProfit + 1];
        dp[0][0] = 1;
        for (int i = 0; i < profit.length; i++) {
            for (int j = n; j >= group[i]; j--) {
                for (int k = minProfit; k >= 0; k--) {
                    dp[j][k] = (dp[j][k] + dp[j - group[i]][Math.max(0, k - profit[i])]) % mod;
                }
            }
        }
        int ans = 0;
        for (int i = 0; i < n + 1; i++) {
            ans = (ans + dp[i][minProfit]) % mod;
        }
        return ans;
    }
}